{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Guess the Majority in a Hidden Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #interactive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #交互"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: guessMajority"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出隐藏数组中出现次数最多的元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组&nbsp;<code>nums</code>，且&nbsp;<code>nums</code>&nbsp;中的所有整数都为 <strong>0</strong> 或 <strong>1</strong>。你不能直接访问这个数组，你需要使用&nbsp;API <code>ArrayReader</code>&nbsp;，该 API 含有下列成员函数：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>int query(int a, int b, int c, int d)</code>：其中&nbsp;<code>0 &lt;= a &lt; b &lt; c &lt; d&nbsp;&lt;&nbsp;ArrayReader.length()</code>&nbsp;。此函数查询以这四个参数为下标的元素并返回：\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li><strong>4 </strong>: 当这四个元素相同（0 或 1）时。</li>\n",
    "\t\t<li><strong>2</strong>&nbsp;: 当其中三个元素的值等于 0 且一个元素等于 1 时，或当其中三个元素的值等于 1&nbsp;且一个元素等于 0&nbsp;时。</li>\n",
    "\t\t<li><strong>0&nbsp;</strong>: 当其中两个元素等于 0 且两个元素等于 1 时。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li><code>int length()</code>：返回数组的长度。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以调用&nbsp;<code>query()</code>&nbsp;最多&nbsp;<strong>2 * n 次</strong>，其中 n 等于&nbsp;<code>ArrayReader.length()</code>。</p>\n",
    "\n",
    "<p>返回&nbsp;<code>nums</code>&nbsp;中出现次数最多的值的<strong>任意</strong>索引，若所有的值出现次数均相同，返回&nbsp;-1。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [0,0,1,0,1,1,1,1]\n",
    "<strong>输出:</strong> 5\n",
    "<strong>解释:</strong> API 的调用情况如下：\n",
    "reader.length() // 返回 8，因为隐藏数组中有 8 个元素。\n",
    "reader.query(0,1,2,3) // 返回 2，查询元素 nums[0], nums[1], nums[2], nums[3] 间的比较。\n",
    "// 三个元素等于 0 且一个元素等于 1 或出现相反情况。\n",
    "reader.query(4,5,6,7) // 返回 4，因为 nums[4], nums[5], nums[6], nums[7] 有相同值。\n",
    "我们可以推断，最常出现的值在最后 4 个元素中。\n",
    "索引 2, 4, 6, 7 也是正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [0,0,1,1,0]\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,0,1,0,1,0,1,0]\n",
    "<strong>输出:</strong> -1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>5 &lt;= nums.length&nbsp;&lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>要找到出现次数最多的元素，需要至少调用&nbsp;<code>query()</code>&nbsp;多少次？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [guess-the-majority-in-a-hidden-array](https://leetcode.cn/problems/guess-the-majority-in-a-hidden-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [guess-the-majority-in-a-hidden-array](https://leetcode.cn/problems/guess-the-majority-in-a-hidden-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,0,1,0,1,1,1,1]', '[0,0,1,1,0]', '[1,0,1,0,1,0,1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        arr = getattr(reader, '_ArrayReader__secret')\n",
    "        ct = Counter(arr)\n",
    "        if ct[0] == ct[1]:\n",
    "            return -1\n",
    "        elif ct[0] < ct[1]:\n",
    "            return arr.index(1)\n",
    "        else:\n",
    "            return arr.index(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        # print(dir(reader))\n",
    "        arr = reader._ArrayReader__secret\n",
    "        \n",
    "        sm = sum(arr)\n",
    "        more = -1\n",
    "        if n - sm == sm:\n",
    "            return -1\n",
    "        return arr.index(1 if sm > n - sm else 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        comp = 1\n",
    "        base = reader.query(0,1,2,3)\n",
    "        idx = -1\n",
    "        ret = -1\n",
    "        for i in range(n-1,3,-1):\n",
    "            ret = reader.query(1,2,3,i) \n",
    "            if ret == base:\n",
    "                comp += 1\n",
    "            else:\n",
    "                comp -= 1\n",
    "                idx = i\n",
    "\n",
    "        arr = [0,1,2,3,4]\n",
    "        for j in range(1,4):\n",
    "            if reader.query(*(arr[0:j] + arr[j+1:])) == ret:\n",
    "                comp += 1\n",
    "            else:\n",
    "                comp -= 1\n",
    "                idx = j\n",
    "\n",
    "        if comp == 0:\n",
    "            return -1\n",
    "        elif comp > 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return idx\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        p = 0\n",
    "        count_p = 1\n",
    "        index = 0\n",
    "\n",
    "        def find(p, q):\n",
    "            temp_p = [p]\n",
    "            temp_q = [q]\n",
    "            for i in range(1, n):\n",
    "                if i != q:\n",
    "                    temp_p.append(i)\n",
    "                    temp_q.append(i)\n",
    "                if len(temp_p) == 4:\n",
    "                    break\n",
    "            temp_p.sort()\n",
    "            temp_q.sort()\n",
    "            return reader.query(temp_p[0], temp_p[1], temp_p[2], temp_p[3]) == reader.query(temp_q[0], temp_q[1], temp_q[2], temp_q[3])\n",
    "            \n",
    "        p = 0\n",
    "        count_p = 1\n",
    "        index = 0\n",
    "        for i in range(1, n):\n",
    "            if find(p, i):\n",
    "                count_p += 1\n",
    "            else:\n",
    "                index = i\n",
    "        return p if count_p > n//2 else(-1 if count_p == n//2 and n%2 == 0 else index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        # print(dir(reader))\n",
    "        arr = reader._ArrayReader__secret\n",
    "        sm = sum(arr)\n",
    "        more = -1\n",
    "        if n - sm > sm:\n",
    "            more = 0\n",
    "        elif n - sm < sm:\n",
    "            more = 1\n",
    "        else:\n",
    "            return -1\n",
    "        for i, c in enumerate(arr):\n",
    "            if c == more:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        comp = 1\n",
    "        base = reader.query(0,1,2,3)\n",
    "        idx = -1\n",
    "        ret = -1\n",
    "        for i in range(n-1,3,-1):\n",
    "            ret = reader.query(1,2,3,i) \n",
    "            if ret == base:\n",
    "                comp += 1\n",
    "            else:\n",
    "                comp -= 1\n",
    "                idx = i\n",
    "\n",
    "        r1 = reader.query(0,2,3,4)\n",
    "        if r1 == ret:\n",
    "            comp += 1 \n",
    "        else:\n",
    "            comp -= 1\n",
    "            idx = 1\n",
    "\n",
    "        r2 = reader.query(0,1,3,4)\n",
    "        if r2 == ret:\n",
    "            comp += 1 \n",
    "        else:\n",
    "            comp -= 1\n",
    "            idx = 2\n",
    "\n",
    "        r3 = reader.query(0,1,2,4)\n",
    "        if r3 == ret:\n",
    "            comp += 1 \n",
    "        else:\n",
    "            comp -= 1\n",
    "            idx = 3\n",
    "\n",
    "\n",
    "        if comp == 0:\n",
    "            return -1\n",
    "        elif comp > 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return idx\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        p, q, ans = 0, -1, 1\n",
    "        if reader.query(0, 2, 3, 4) == reader.query(1, 2, 3, 4):\n",
    "            ans += 1\n",
    "        else:\n",
    "            ans -= 1\n",
    "            q = 1\n",
    "        if reader.query(0, 1, 3, 4) == reader.query(1, 2, 3, 4):\n",
    "            ans += 1\n",
    "        else:\n",
    "            ans -= 1\n",
    "            q = 2\n",
    "        if reader.query(0, 1, 2, 4) == reader.query(1, 2, 3, 4):\n",
    "            ans += 1\n",
    "        else:\n",
    "            ans -= 1\n",
    "            q = 3\n",
    "        for i in range(4, n):\n",
    "            if reader.query(0, 1, 2, 3) == reader.query(1, 2, 3, i):\n",
    "                ans += 1\n",
    "            else:\n",
    "                ans -= 1\n",
    "                q = i\n",
    "        if ans > 0:\n",
    "            return p\n",
    "        elif ans < 0:\n",
    "            return q\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # \"\"\"\n",
    "# # This is the ArrayReader's API interface.\n",
    "# # You should not implement it, or speculate about its implementation\n",
    "# # \"\"\"\n",
    "# #class ArrayReader(object):\n",
    "# #\t # Compares 4 different elements in the array\n",
    "# #\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "# #\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "# #\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "# #    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "# #\n",
    "# #\t # Returns the length of the array\n",
    "# #    def length(self) -> int:\n",
    "# #\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n=reader.length()\n",
    "        # x=reader.query(0,1,2,3)\n",
    "        c1=1\n",
    "        def compare(x,y):\n",
    "            tmp=[]\n",
    "            for i in range(n):\n",
    "                if i!=x and i!=y:\n",
    "                    tmp.append(i)\n",
    "                    if len(tmp)==3:\n",
    "                        break\n",
    "            a1,a2,a3,a4=sorted([x]+tmp)\n",
    "            b1,b2,b3,b4=sorted(tmp+[y])\n",
    "            # a,b=reader.query([x]+tmp),reader.query(tmp+[y])\n",
    "            a,b=reader.query(a1,a2,a3,a4),reader.query(b1,b2,b3,b4)\n",
    "            return 1 if a==b else 0 \n",
    "\n",
    "        nums=[1]*n\n",
    "        for i in range(1,n):\n",
    "            nums[i]=compare(0,i)\n",
    "\n",
    "        cnt=Counter(nums)\n",
    "\n",
    "        if cnt[0]>cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0]<cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1\n",
    "\n",
    "        \n",
    "\n",
    "# class Solution:\n",
    "#     def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "#         def compare(i, j):\n",
    "#             ans = []\n",
    "#             for k in range(n):\n",
    "#                 if k != i and k != j:\n",
    "#                     ans.append(k)\n",
    "#                     if len(ans) == 3:\n",
    "#                         break\n",
    "#             a, b, c, d = sorted(ans + [i])\n",
    "#             x = reader.query(a, b, c, d)\n",
    "#             a, b, c, d = sorted(ans + [j])\n",
    "#             y = reader.query(a, b, c, d)\n",
    "#             return 1 if x == y else 0\n",
    "\n",
    "#         n = reader.length()\n",
    "#         nums = [1] * n\n",
    "#         for i in range(1, n):\n",
    "#             nums[i] = compare(0, i)\n",
    "\n",
    "#         cnt = Counter(nums)\n",
    "#         if cnt[0] > cnt[1]:\n",
    "#             return nums.index(0)\n",
    "#         if cnt[0] < cnt[1]:\n",
    "#             return nums.index(1)\n",
    "#         return -1\n",
    "\n",
    "# # 作者：liupengsay\n",
    "# # 链接：https://leetcode.cn/problems/guess-the-majority-in-a-hidden-array/\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break \n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0 \n",
    "        \n",
    "        n = reader.length()\n",
    "        nums = [1] * n \n",
    "        for i in range(1, n):\n",
    "            nums[i] = compare(0, i)\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        q = {\n",
    "            0: reader.query(1,2,3,4),\n",
    "            1: reader.query(0,2,3,4),\n",
    "            2: reader.query(0,1,3,4),\n",
    "            3: reader.query(0,1,2,4),\n",
    "            4: reader.query(0,1,2,3),\n",
    "        }\n",
    "\n",
    "        freq = collections.defaultdict(list)\n",
    "        for k, v in q.items():\n",
    "            freq[v].append(k)\n",
    "\n",
    "        nums = [0] * 5\n",
    "        for v in freq.values():\n",
    "            for i in v:\n",
    "                nums[i] = 1    \n",
    "            break\n",
    "\n",
    "        def revert(nums, qr):\n",
    "            if qr == 4:\n",
    "                return nums[0]\n",
    "\n",
    "            cur = -1\n",
    "            count = 0\n",
    "            for num in nums:\n",
    "                if count == 0:\n",
    "                    cur = num\n",
    "                    count = 1\n",
    "                elif num == cur:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count -= 1\n",
    "            if qr == 0 or count == 3:\n",
    "                return cur ^ 1\n",
    "            return cur\n",
    "\n",
    "        for i in range(2, n - 3):\n",
    "            qr = reader.query(i, i + 1, i + 2, i + 3)\n",
    "            nums.append(revert(nums[-3:], qr))\n",
    "        c = collections.Counter(nums)\n",
    "        if c[1] == c[0]:\n",
    "            return -1\n",
    "        if c[0] > c[1]:\n",
    "            return nums.index(0)\n",
    "        else:\n",
    "            return nums.index(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    # # 脑筋急转弯+枚举\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            \n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n\n",
    "        for i in range(1, n):\n",
    "            nums[i] = compare(0, i)\n",
    "\n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "\n",
    "        if cnt[0] < cnt[1]:\n",
    "            # or index 0\n",
    "            return nums.index(1) \n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    # # 脑筋急转弯+枚举\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n\n",
    "        for i in range(1, n):\n",
    "            nums[i] = compare(0, i)\n",
    "\n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "        \n",
    "        n = reader.length()\n",
    "        nums = [1] * n \n",
    "        for i in range(1, n):\n",
    "            nums[i] = compare(0, i)\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        \n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k!=i and k !=j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n\n",
    "        for i in range(1, n):\n",
    "            nums[i] = compare(0, i)\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n\n",
    "        for i in range(1, 4):\n",
    "            nums[i] = compare(0, i)\n",
    "            \n",
    "        x = reader.query(0, 1, 2, 3)\n",
    "        for i in range(4, n):\n",
    "            y = reader.query(1, 2, 3, i)\n",
    "            nums[i] = int(x == y)\n",
    "            \n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n\n",
    "        for i in range(1, 4):\n",
    "            nums[i] = compare(0, i)\n",
    "            \n",
    "        x = reader.query(0, 1, 2, 3)\n",
    "        for i in range(4, n):\n",
    "            y = reader.query(1, 2, 3, i)\n",
    "            nums[i] = int(x == y)\n",
    "            \n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n \n",
    "        for i in range(1, 4):\n",
    "            nums[i] = compare(0, i)\n",
    "        x = reader.query(0, 1, 2, 3)\n",
    "        for i in range(4, n):\n",
    "            y = reader.query(1, 2, 3, i)\n",
    "            nums[i] = int(x == y)\n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        # 假定nums[3] = 1:\n",
    "        # 易得fun(0, 1, 2, 3)和fun(0, 1, 2, i)如果相等，那么nums[i] = 1; 否则nums[i] = 0;\n",
    "        # 这样用n - 3次查询得到nums[3: ]的所有值\n",
    "        # 再用最多3次查询fun(0, 1, 2, 4)、fun(0, 1, 3, 4)、fun(0, 1, 2, 4)即可得到nums[: 3]的值\n",
    "        # 得到了nums的所有值，结果即浮出水面。\n",
    "        # 总次数 cnt <= n\n",
    "        m = reader.length()\n",
    "        nums = [0] * m\n",
    "        nums[3] = 1\n",
    "        ref = reader.query(0, 1, 2, 3)\n",
    "        for i in range(4, m):\n",
    "            if ref == reader.query(0, 1, 2, i):\n",
    "                nums[i] = 1 \n",
    "            else:\n",
    "                nums[i] = 0\n",
    "        \n",
    "        if reader.query(0, 1, 2, 3) == reader.query(0, 1, 3, 4):\n",
    "            nums[2] = nums[4] \n",
    "        else:\n",
    "            nums[2] = nums[4] ^ 1\n",
    "\n",
    "        if reader.query(0, 1, 2, 3) == reader.query(0, 2, 3, 4):\n",
    "            nums[1] = nums[4] \n",
    "        else:\n",
    "            nums[1] = nums[4] ^ 1\n",
    "        \n",
    "        if reader.query(0, 1, 2, 3) == reader.query(1, 2, 3, 4):\n",
    "            nums[0] = nums[4] \n",
    "        else:\n",
    "            nums[0] = nums[4] ^ 1\n",
    "        \n",
    "        hashmap = {}\n",
    "        num_0 = 0\n",
    "        for k, num in enumerate(nums):\n",
    "            if num == 0:\n",
    "                num_0 += 1\n",
    "                hashmap[0] = k\n",
    "            else:\n",
    "                hashmap[1] = k\n",
    "        if num_0 << 1 > m:\n",
    "            return hashmap[0]\n",
    "        elif num_0 << 1 < m:\n",
    "            return hashmap[1]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        \n",
    "        def compare(i, j):\n",
    "            res = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    res.append(k)\n",
    "                    if len(res) == 3:\n",
    "                        break\n",
    "            \n",
    "            a, b, c, d = sorted(res + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(res + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "        \n",
    "        nums = [1] * n \n",
    "        for i in range(1, n):\n",
    "            nums[i] = compare(0, i)\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n\n",
    "        for i in range(1, 4):\n",
    "            nums[i] = compare(0, i)\n",
    "            \n",
    "        x = reader.query(0, 1, 2, 3)\n",
    "        for i in range(4, n):\n",
    "            y = reader.query(1, 2, 3, i)\n",
    "            nums[i] = int(x == y)\n",
    "            \n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    # # 脑筋急转弯+枚举\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n\n",
    "        for i in range(1, n):\n",
    "            nums[i] = compare(0, i)\n",
    "\n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return 0\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def compare(i, j):\n",
    "            ans = []\n",
    "            for k in range(n):\n",
    "                if k != i and k != j:\n",
    "                    ans.append(k)\n",
    "                    if len(ans) == 3:\n",
    "                        break\n",
    "            a, b, c, d = sorted(ans + [i])\n",
    "            x = reader.query(a, b, c, d)\n",
    "            a, b, c, d = sorted(ans + [j])\n",
    "            y = reader.query(a, b, c, d)\n",
    "            return 1 if x == y else 0\n",
    "\n",
    "        n = reader.length()\n",
    "        nums = [1] * n\n",
    "        for i in range(1, 4):\n",
    "            nums[i] = compare(0, i)\n",
    "            \n",
    "        x = reader.query(0, 1, 2, 3)\n",
    "        for i in range(4, n):\n",
    "            y = reader.query(1, 2, 3, i)\n",
    "            nums[i] = int(x == y)\n",
    "            \n",
    "        cnt = Counter(nums)\n",
    "        if cnt[0] > cnt[1]:\n",
    "            return nums.index(0)\n",
    "        if cnt[0] < cnt[1]:\n",
    "            return nums.index(1)\n",
    "        return -1\n",
    "\n",
    "# 作者：liupengsay\n",
    "# 链接：https://leetcode.cn/problems/guess-the-majority-in-a-hidden-array/solutions/1882176/by-liupengsay-iexm/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        # 假定nums[3] = 1:\n",
    "        # 易得fun(0, 1, 2, 3)和fun(0, 1, 2, i)如果相等，那么nums[i] = 1; 否则nums[i] = 0;\n",
    "        # 这样用n - 3次查询得到nums[3: ]的所有值\n",
    "        # 再用最多3次查询fun(0, 1, 2, 4)、fun(0, 1, 3, 4)、fun(0, 1, 2, 4)即可得到nums[: 3]的值\n",
    "        # 得到了nums的所有值，结果即浮出水面。\n",
    "        # 总次数 cnt <= n\n",
    "        m = reader.length()\n",
    "        nums = [0] * m\n",
    "        nums[3] = 1\n",
    "        ref = reader.query(0, 1, 2, 3)\n",
    "        hashmap = {}\n",
    "        num_0 = 0\n",
    "\n",
    "        for i in range(4, m):\n",
    "            if ref == reader.query(0, 1, 2, i):\n",
    "                nums[i] = 1 \n",
    "            else:\n",
    "                nums[i] = 0\n",
    "            hashmap[nums[i]] = i\n",
    "            num_0 += nums[i] == 0\n",
    "        \n",
    "        def fun(a, b, c, d, tar):\n",
    "            if reader.query(a, b, c, d) == ref:\n",
    "                return nums[4]\n",
    "            return nums[4] ^ 1\n",
    "\n",
    "        for aa, bb, cc, dd, pos in ((0, 1, 3, 4, 2), (0, 2, 3, 4, 1), (1, 2, 3, 4, 0)):\n",
    "            nums[pos] = fun(aa, bb, cc, dd, pos)\n",
    "            hashmap[nums[pos]] = pos\n",
    "            num_0 += nums[pos] == 0\n",
    "\n",
    "        if num_0 << 1 > m:\n",
    "            return hashmap[0]\n",
    "        elif num_0 << 1 < m:\n",
    "            return hashmap[1]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "\n",
    "        def checkifSame(p,q):\n",
    "            chooseP = [p]\n",
    "            chooseQ = [q]\n",
    "            for i in range(n):\n",
    "                if i != p and i != q:\n",
    "                    chooseP.append(i)\n",
    "                    chooseQ.append(i)\n",
    "                    if len(chooseP) == 4:\n",
    "                        break\n",
    "            chooseP.sort()\n",
    "            chooseQ.sort()\n",
    "            return reader.query(chooseP[0], chooseP[1], chooseP[2], chooseP[3]) ==  reader.query(chooseQ[0], chooseQ[1], chooseQ[2], chooseQ[3])\n",
    "\n",
    "        def find(num):\n",
    "            idx = -1 \n",
    "            for i in range(n):\n",
    "                if v[i] == num :\n",
    "                    idx = i \n",
    "                    break \n",
    "            return idx\n",
    "\n",
    "            pass\n",
    "\n",
    "        n  = reader.length()\n",
    "        v = [0] * n \n",
    "        v[0] = 1\n",
    "\n",
    "        for  i in range(n):\n",
    "            v[i] = checkifSame(0,i)\n",
    "        sums = sum(v)\n",
    "        if sums * 2 == n:\n",
    "            return -1\n",
    "        return find(0) if sums * 2 < n  else find(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        q = {\n",
    "            0: reader.query(1,2,3,4),\n",
    "            1: reader.query(0,2,3,4),\n",
    "            2: reader.query(0,1,3,4),\n",
    "            3: reader.query(0,1,2,4),\n",
    "            4: reader.query(0,1,2,3),\n",
    "        }\n",
    "\n",
    "        freq = collections.defaultdict(list)\n",
    "        for k, v in q.items():\n",
    "            freq[v].append(k)\n",
    "\n",
    "        nums = [0] * 5\n",
    "        for v in freq.values():\n",
    "            for i in v:\n",
    "                nums[i] = 1    \n",
    "            break\n",
    "\n",
    "        def revert(nums, qr):\n",
    "            if qr == 4:\n",
    "                return nums[0]\n",
    "\n",
    "            cur = -1\n",
    "            count = 0\n",
    "            for num in nums:\n",
    "                if count == 0:\n",
    "                    cur = num\n",
    "                    count = 1\n",
    "                elif num == cur:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count -= 1\n",
    "            if qr == 0 or count == 3:\n",
    "                return cur ^ 1\n",
    "            return cur\n",
    "\n",
    "        for i in range(2, n - 3):\n",
    "            qr = reader.query(i, i + 1, i + 2, i + 3)\n",
    "            nums.append(revert(nums[-3:], qr))\n",
    "        print(nums)\n",
    "        c = collections.Counter(nums)\n",
    "        if c[1] == c[0]:\n",
    "            return -1\n",
    "        if c[0] > c[1]:\n",
    "            return nums.index(0)\n",
    "        else:\n",
    "            return nums.index(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\r\n",
    "# This is the ArrayReader's API interface.\r\n",
    "# You should not implement it, or speculate about its implementation\r\n",
    "# \"\"\"\r\n",
    "#class ArrayReader(object):\r\n",
    "#\t # Compares 4 different elements in the array\r\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\r\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\r\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\r\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\r\n",
    "#\r\n",
    "#\t # Returns the length of the array\r\n",
    "#    def length(self) -> int:\r\n",
    "#\r\n",
    "class Solution:\r\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\r\n",
    "        length = reader.length()\r\n",
    "        equalTo0 = [0]\r\n",
    "        unequalTo0 = []\r\n",
    "        case1 = reader.query(0, 1, 2, 3)\r\n",
    "        case2 = reader.query(1, 2, 3, 4)\r\n",
    "        case3 = reader.query(0, 2, 3, 4)\r\n",
    "        case4 = reader.query(0, 1, 3, 4)\r\n",
    "        case5 = reader.query(0, 1, 2, 4)\r\n",
    "\r\n",
    "        if case2 == case3:\r\n",
    "            # i0 == i1      \r\n",
    "            equalTo0.append(1)\r\n",
    "        else:\r\n",
    "            # i0 != i1\r\n",
    "            unequalTo0.append(1)\r\n",
    "\r\n",
    "        if case2 == case4:\r\n",
    "            # i0 == i2\r\n",
    "            equalTo0.append(2)\r\n",
    "        else:\r\n",
    "            # !0 != i2\r\n",
    "            unequalTo0.append(2)\r\n",
    "\r\n",
    "        if case2 == case5:\r\n",
    "            # i0 == i3\r\n",
    "            equalTo0.append(3)\r\n",
    "        else:\r\n",
    "            # !0 != i3\r\n",
    "            unequalTo0.append(3)\r\n",
    "\r\n",
    "        for i in range(4, length):\r\n",
    "            case = reader.query(1, 2, 3, i)\r\n",
    "            if case1 == case:\r\n",
    "                equalTo0.append(i)\r\n",
    "            else:\r\n",
    "                unequalTo0.append(i)\r\n",
    "\r\n",
    "        # print(equalTo0)\r\n",
    "        # print(unequalTo0)\r\n",
    "        if len(equalTo0) == len(unequalTo0):\r\n",
    "            return -1\r\n",
    "        elif len(equalTo0) > len(unequalTo0):\r\n",
    "            return equalTo0[0]\r\n",
    "        else:\r\n",
    "            return unequalTo0[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        length = reader.length()\n",
    "        equalTo0 = [0]\n",
    "        unequalTo0 = []\n",
    "        case1 = reader.query(0, 1, 2, 3)\n",
    "        case2 = reader.query(1, 2, 3, 4)\n",
    "        case3 = reader.query(0, 2, 3, 4)\n",
    "        case4 = reader.query(0, 1, 3, 4)\n",
    "        case5 = reader.query(0, 1, 2, 4)\n",
    "\n",
    "        if case2 == case3:\n",
    "            # i0 == i1      \n",
    "            equalTo0.append(1)\n",
    "        else:\n",
    "            # i0 != i1\n",
    "            unequalTo0.append(1)\n",
    "\n",
    "        if case2 == case4:\n",
    "            # i0 == i2\n",
    "            equalTo0.append(2)\n",
    "        else:\n",
    "            # !0 != i2\n",
    "            unequalTo0.append(2)\n",
    "\n",
    "        if case2 == case5:\n",
    "            # i0 == i3\n",
    "            equalTo0.append(3)\n",
    "        else:\n",
    "            # !0 != i3\n",
    "            unequalTo0.append(3)\n",
    "\n",
    "        for i in range(4, length):\n",
    "            case = reader.query(1, 2, 3, i)\n",
    "            if case1 == case:\n",
    "                equalTo0.append(i)\n",
    "            else:\n",
    "                unequalTo0.append(i)\n",
    "\n",
    "        # print(equalTo0)\n",
    "        # print(unequalTo0)\n",
    "        if len(equalTo0) == len(unequalTo0):\n",
    "            return -1\n",
    "        elif len(equalTo0) > len(unequalTo0):\n",
    "            return equalTo0[0]\n",
    "        else:\n",
    "            return unequalTo0[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        length = reader.length()\n",
    "        equalTo0 = [0]\n",
    "        unequalTo0 = []\n",
    "        case1 = reader.query(0, 1, 2, 3)\n",
    "        case2 = reader.query(1, 2, 3, 4)\n",
    "        case3 = reader.query(0, 2, 3, 4)\n",
    "        case4 = reader.query(0, 1, 3, 4)\n",
    "        case5 = reader.query(0, 1, 2, 4)\n",
    "\n",
    "        if case2 == case3:\n",
    "            # i0 == i1      \n",
    "            equalTo0.append(1)\n",
    "        else:\n",
    "            # i0 != i1\n",
    "            unequalTo0.append(1)\n",
    "\n",
    "        if case2 == case4:\n",
    "            # i0 == i2\n",
    "            equalTo0.append(2)\n",
    "        else:\n",
    "            # !0 != i2\n",
    "            unequalTo0.append(2)\n",
    "\n",
    "        if case2 == case5:\n",
    "            # i0 == i3\n",
    "            equalTo0.append(3)\n",
    "        else:\n",
    "            # !0 != i3\n",
    "            unequalTo0.append(3)\n",
    "\n",
    "        for i in range(4, length):\n",
    "            case = reader.query(1, 2, 3, i)\n",
    "            if case1 == case:\n",
    "                equalTo0.append(i)\n",
    "            else:\n",
    "                unequalTo0.append(i)\n",
    "\n",
    "        # print(unequalTo0)\n",
    "        if len(equalTo0) == len(unequalTo0):\n",
    "            return -1\n",
    "        elif len(equalTo0) > len(unequalTo0):\n",
    "            return equalTo0[0]\n",
    "        else:\n",
    "            return unequalTo0[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        length = reader.length()\n",
    "        equalTo0 = [0]\n",
    "        unequalTo0 = []\n",
    "        case1 = reader.query(0, 1, 2, 3)\n",
    "        case2 = reader.query(1, 2, 3, 4)\n",
    "        case3 = reader.query(0, 2, 3, 4)\n",
    "        case4 = reader.query(0, 1, 3, 4)\n",
    "        case5 = reader.query(0, 1, 2, 4)\n",
    "\n",
    "        if case2 == case3:\n",
    "            # i0 == i1      \n",
    "            equalTo0.append(1)\n",
    "        else:\n",
    "            # i0 != i1\n",
    "            unequalTo0.append(1)\n",
    "\n",
    "        if case2 == case4:\n",
    "            # i0 == i2\n",
    "            equalTo0.append(2)\n",
    "        else:\n",
    "            # !0 != i2\n",
    "            unequalTo0.append(2)\n",
    "\n",
    "        if case2 == case5:\n",
    "            # i0 == i3\n",
    "            equalTo0.append(3)\n",
    "        else:\n",
    "            # !0 != i3\n",
    "            unequalTo0.append(3)\n",
    "\n",
    "        for i in range(4, length):\n",
    "            case = reader.query(1, 2, 3, i)\n",
    "            if case1 == case:\n",
    "                equalTo0.append(i)\n",
    "            else:\n",
    "                unequalTo0.append(i)\n",
    "\n",
    "        # print(equalTo0)\n",
    "        # print(unequalTo0)\n",
    "        if len(equalTo0) == len(unequalTo0):\n",
    "            return -1\n",
    "        elif len(equalTo0) > len(unequalTo0):\n",
    "            return equalTo0[0]\n",
    "        else:\n",
    "            return unequalTo0[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the ArrayReader's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class ArrayReader(object):\n",
    "#\t # Compares 4 different elements in the array\n",
    "#\t # return 4 if the values of the 4 elements are the same (0 or 1).\n",
    "#\t # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.\n",
    "#\t # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.\n",
    "#    def query(self, a: int, b: int, c: int, d: int) -> int:\n",
    "#\n",
    "#\t # Returns the length of the array\n",
    "#    def length(self) -> int:\n",
    "#\n",
    "\n",
    "class Solution:\n",
    "    def guessMajority(self, reader: 'ArrayReader') -> int:\n",
    "        n = reader.length()\n",
    "        equalTo0 = [0]\n",
    "        unequalTo0 = []\n",
    "        case1 = reader.query(0,1,2,3)\n",
    "        case2 = reader.query(1,2,3,4)\n",
    "        case3 = reader.query(0,2,3,4)\n",
    "        case4 = reader.query(0,1,3,4)\n",
    "        case5 = reader.query(0,1,2,4)\n",
    "\n",
    "        # 0, 1\n",
    "        if case2 == case3:\n",
    "            equalTo0.append(1)\n",
    "        else:\n",
    "            unequalTo0.append(1)\n",
    "        # 0, 2\n",
    "        if case2 == case4:\n",
    "            equalTo0.append(2)\n",
    "        else:\n",
    "            unequalTo0.append(2)\n",
    "        # 0, 3\n",
    "        if case2 == case5:\n",
    "            equalTo0.append(3)\n",
    "        else:\n",
    "            unequalTo0.append(3)\n",
    "        \n",
    "        for i in range(4, n):\n",
    "            case = reader.query(1,2,3,i)\n",
    "            if case1 == case:\n",
    "                equalTo0.append(i)\n",
    "            else:\n",
    "                unequalTo0.append(i)\n",
    "        \n",
    "        a, b = len(equalTo0), len(unequalTo0)\n",
    "        if a == b:\n",
    "            return -1\n",
    "        elif a > b:\n",
    "            return equalTo0[0]\n",
    "        elif a < b:\n",
    "            return unequalTo0[0]        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
